package fun.ticsmyc.math;

import fun.ticsmyc.tools.ArrayTools;
import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * m个数中等概率拿n个
 * @author Ticsmyc
 * @date 2020-12-23 10:38
 */
public class 蓄水池抽样 {

    @Test
    public void test(){
        int[] count = new int[11];
        for(int i=0;i<100000;++i){
            int[] arr = new int[]{1,2,3,4,5,6,7,8,9,10};
            int[] r = fun(arr,2);
            count[r[0]]++;
            count[r[1]]++;
        }
        ArrayTools.printArray(count);
    }

    /**
     * 从arr中等概率取出n个数
     * @param arr
     * @param n
     * @return
     */
    public int[] fun(int[] arr, int n){
        int[] ans = new int[n];
        for(int i=0;i<n;++i){
            ans[i]=arr[i];
        }

        Random r = new Random();
        for(int i=n;i<arr.length;++i){
            int tmp= r.nextInt(i+1);
            if(tmp<n){
                ans[tmp] = arr[i];
            }
        }
        return ans;
    }
    public int[] fun2(int[] arr, int n){
        Random r = new Random();
        for(int i=n;i<arr.length;++i){
            int tmp= r.nextInt(i+1);
            arr[tmp] = arr[i];
        }
        return Arrays.copyOf(arr,n);
    }

}
